/**
 * 请判断一个链表是否为回文链表。
 *  输入: 1->2
 *  输出: false
 *
 * 输入: 1->2->2->1
 * 输出: true
 */


/**
 * @param {ListNode} head
 * @return {boolean}
 */

const Node = require('../../单链表/node')
var isPalindrome = function (head) {
    if (!head || !head.next) return true
    let mid = head
    let fast = head
    while (fast.next !== null && fast.next.next !== null) {
        fast = fast.next.next
        mid = mid.next
    }
    let p = mid.next
    let r = p.next
    mid.next = null
    while (p !== null) {
        p.next = mid.next
        mid.next = p
        p = r
        if (r !== null) {
            r = r.next
        }
    }
    let first = new Node
    first.next = head
    first = first.next
    mid = mid.next
    while (mid !== null) {
        if (first.data !== mid.data) break
        first = first.next
        mid = mid.next
    }
    return mid === null ? true : false
};


let head = new Node(1)
head.next = new Node(2)
head.next.next = new Node(1)
console.log(head)
console.log(isPalindrome(head));


// ============================= 递归===================================
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
    // 左指针
    let lhead = head;
    // 递归定义：倒序遍历以rhead为头的链表，返回布尔值判断其是否为回文链表
    let tranverse = (rhead) => {
        if (!rhead) return true;
        // 后序遍历形式，从最后一个开始判断
        let res = tranverse(rhead.next);
        res = res && (lhead.val === rhead.val);
        lhead = lhead.next;
        return res;
    }
    return tranverse(head);
};

// ============================辅助栈=============================
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
    if (!head || !head.next) return true;
    let slow = head, fast = head, flag = true;
    // 创建辅助栈
    let auxStack = [];

    // 寻找中位
    while (fast !== null && fast.next !== null) {
        auxStack.push(slow.val);
        slow = slow.next;
        fast = fast.next.next;
    }
    // 处理奇数
    if (fast && !fast.next) {
        slow = slow.next;
    }
    // 逐个对比
    // debugger;
    while (auxStack.length !== 0) {

        let popVal = auxStack.pop();
        if (slow.val !== popVal) {
            flag = false;
            return flag;
        }
        slow = slow.next;
    }
    return flag;
};